Рекуррентное соотношение

**Рекуррентное соотношение (от одной переменной)** — уравнение, задающее функцию натурального аргумента $n$ через ее значения при меньших $n$. Функция натурального аргумента и последовательность — это одно и то же. Условно-формальная запись: $f(0) = c, f(n) = F(n, f(0), \dots, f(n-1))$

**Рекуррентное соотношение k-го порядка** — это соотношение вида: $$f(n) = F(n, f(n-1), \dots, f(n-k))$$ Здесь $F$ — «нормальная» $(k+1)$-местная функция. Для задания функции таким соотношением нужно $k$ начальных значений $f(0), \dots, f(k-1)$. Рекуррентное соотношение $f(n) = F(n, f(n-1), \dots, f(n-k))$ называется: - **линейным**, если $F = F(x_1, \dots, x_k)$ — линейная функция с коэффициентами, зависящими от параметра $n$, т.е. $$f(n) = a_1(n)f(n-1) + \dots + a_k(n)f(n-k) + a(n)$$ - **линейным однородным**, если $a(n) = 0$. - **линейным с постоянными коэффициентами**, если все $a_i(n)$ — константы ($a(n)$ может не быть константой).